package com.base.greedy;

import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName FullJustify
 * @Description 68. 文本左右对齐
 * 给定一个单词数组和一个长度maxWidth，重新排版单词，使其成为每行恰好有maxWidth个字符，且左右两端对齐的文本。
 * <p>
 * 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格' '填充，使得每行恰好有 maxWidth个字符。
 * <p>
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 * <p>
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/text-justification
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 说明:
 * <p>
 * 单词是指由非空格字符组成的字符序列。
 * 每个单词的长度大于 0，小于等于 maxWidth。
 * 输入单词数组 words 至少包含一个单词。
 * @Author li
 * Date 2021/9/9 19:10
 * Copyright
 **/
public class FullJustify {
    /**
     * 1.贪心策略：每一行尽可能多的单词，必须满足所有单词的长度+(所有单词数-1)<=weight;
     * 2.如果正好==；则是最佳的
     * 3.如果是<；
     * 4.则需要满足a = （weight-所有单词长度）/ （所有单词数-1） -----向下取整， b = （weight-所有单词长度）mod （所有单词数-1）;
     * 5.如果是3的条件，则前b个间隔是a+1个空格，剩下的是a个空格
     * 6.如果单词数是1，则不必进行3，4的计算，直接在后面增加相应的空格是字符串达到weight长度就可以了
     *
     * @param words  单词数组
     * @param weight 每行的最大长度
     * @return 对齐后的字符串列表
     */
    public List<String> fullJustify(String[] words, int weight) {
        List<String> res = new LinkedList<>();
        if (words.length == 0){
            return res;
        }

        int left = 0,right = 1;
        for (; right < words.length ; right++) {
            int total = words[left].length();
            StringBuilder stringBuilder = new StringBuilder();
            while (right< words.length&&total+words[right].length()+right-left<=weight){
                total+=words[right].length();
                right++;
            }
            if (right>=words.length){
                stringBuilder.append(words[left]);
                while (left+1<right){
                    stringBuilder.append(" ");
                    stringBuilder.append(words[left+1]);
                    left++;
                }
                int len =stringBuilder.length();
                for (int i = 0; i < weight -len; i++) {
                    stringBuilder.append(" ");
                }
                res.add(stringBuilder.toString());
                left++;
                break;
            }
            if (total+right-left-1==weight){
                stringBuilder.append(words[left]);
                for (int i = left+1; i < right; i++) {
                    stringBuilder.append(" ");
                    stringBuilder.append(words[i]);
                }
            }else if (total+right-left-1<weight){

                if (right-left==1){
                    stringBuilder.append(words[left]);
                    for (int i = 0; i < weight - words[left].length(); i++) {
                        stringBuilder.append(" ");
                    }

                }else {
                    int a = (weight - total) / (right - left -1);
                    int b = (weight - total) % (right - left -1);
                    stringBuilder.append(words[left]);
                    for (int i = left+1; i < right; i++) {
                        if (b>0){
                            for (int j = 0; j < a+1; j++) {
                                stringBuilder.append(" ");
                            }
                            b--;
                        }else {
                            for (int j = 0; j < a; j++) {
                                stringBuilder.append(" ");
                            }
                        }
                        stringBuilder.append(words[i]);
                    }
                }
            }
            res.add(stringBuilder.toString());
            left = right;

        }
        if (left< words.length){
            StringBuilder stringBuilder =new StringBuilder();
            stringBuilder.append(words[left]);
            for (int i = 0; i < weight - words[left].length(); i++) {
                stringBuilder.append(" ");
            }
            res.add(stringBuilder.toString());
        }
        return res;
    }
}
